Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

摘要

We study the behavior of Approximate Message-Passing, a solver for linearsparse estimation problems such as compressed sensing, when the i.i.d matrices-for which it has been specifically designed- are replaced by structuredoperators, such as Fourier and Hadamard ones. We show empirically that afterproper randomization, the structure of the operators does not significantlyaffect the performances of the solver. Furthermore, for some specially designedspatially coupled operators, this allows a computationally fast and memoryefficient reconstruction in compressed sensing up to theinformation-theoretical limit. We also show how this approach can be applied tosparse superposition codes, allowing the Approximate Message-Passing decoder toperform at large rates for moderate block length.